A prevalent load spreading technique today is the spreading of traffic over a set of equal cost paths to a destination node referred to as equal cost multi-path (ECMP). However, in some implementations ECMP can have limitations in supporting operation, administration and management (OAM) functions and difficulties in evenly spreading a traffic load in asymmetrical topologies. ECMP has been implemented by using hashing algorithms and/or modulo operations on labels for multi-protocol label switching (MPLS) traffic, virtual local area network IDs (VLAN IDs) for layer 2 technologies, or header information from packets for layer 3 technology. These hashing algorithms and modulo operations are utilized to spread data traffic streams over the number of equal cost next hops in a network as a next hop selection mechanism for forwarding data traffic.
When a network forwarding device supports ECMP and this capability is enabled and there are multiple paths with the same (or similar) cost towards a specific destination, the network forwarding device will attempt to divide the load evenly across the set of equal cost next hops. Numerous techniques exist for distributing traffic over these equal cost next hops, those techniques with the most desirable properties are those that preserve flow ordering among protocol data units (PDUs), that is, all PDUs that have similar characteristics such as source, destination and header information, can be considered part of the same “flow” and preserving their ordering indicates that they arrive at their destination in the same order that they were sent by the source.
Existing load spreading techniques rely on the use of some form of hashing process that is applied per-PDU by a network forwarding device. Using such hashing techniques allows for large-scale determination of a collection of “flows” based on key fields in a PDU header. For example, a subset of source address and destination address bits can be used as input to a hashing function to group “flows” in such a way that all PDUs traveling from a particular source to a particular destination are considered part of the same gross-flow and forwarding all PDUs that are part of this gross-flow guarantees that no PDU within a subset flow will follow a different path and as a consequence potentially arrive out of order from the rest of the flow.
ECMP and similar hashing-based techniques have limitations in that in any irregular network or in any regular network that is in a failure scenario these techniques have difficulties with distributing the load evenly across the plurality of equal cost paths. This is because any particular hashing scheme that is selected in an attempt to evenly distribute PDU traffic across the set of paths is selected without regard to the actual layout of the network beyond the immediate set of next hops. The hashing scheme is typically not changed dynamically in a network failure scenario due to the disruption that would be caused, as a result the hashing scheme selected may not produce substantially even load distribution in the changed network topology.